﻿#pragma once
# include<iostream>
using namespace std;

enum Colour
{
	RED,
	BLACK
};

template <class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;
	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};
template<class K, class V>
class RBTree
{
public:
     typedef RBTreeNode<K, V> Node;
	 bool insert(const pair<K, V>& kv)
	 {
		 if (_root == nullptr)  //对空树的处理
		 {
			 _root = new Node(kv);
			 _root->_col = BLACK;    //根节点一定是黑色
			 return true;
		 } 
		 Node* cur = _root;
		 Node* curparent = cur;
		 while (cur != nullptr)              //直到为空了  就是要插入的位置
		 {
			 if (kv.first > cur->_kv.first)             //要插入的数大于根的值就往右
			 {
				 curparent = cur;          //cur里面存的是cur的上一个位置 cur改变之前先把它的位置存到curparent中
				 cur = cur->_right;
			 }
			 else if (kv.first < cur->_kv.first)       //小于根的值就往左
			 {
				 curparent = cur;
				 cur = cur->_left;
			 }
			 else
				 return false;        //不支持插入重复的元素 插入失败 返回false
		 }

		 //如果正常出了循环 那么此时cur的位置就是新插入节点的位置 那么此时为新节点开空间 然后让它的父节点指向它
		 cur = new Node(kv);
		 if (curparent->_kv.first < kv.first)
			 curparent->_right = cur;          //此时还需要判断 cur位置的节点是父节点的右孩子还是左孩子
		 else
			 curparent->_left = cur;

		 cur->_parent = curparent;           //处理节点的parent指针
		 cur->_col = RED;       //新插入的非根节点一定是红色的
		 while (curparent&&curparent->_col == RED)         //这样用while是针对u存在且为红的情况
		 {                                       //通过处理这种情况 当grandparent为根节点再更新cur后此时的curparent为空所以需要判空
			 Node* grandparent = curparent->_parent;  //g
			 Node* uncle = nullptr;

			 if (curparent->_kv.first<grandparent->_kv.first)         //uncle为g的另一个孩子节点
			 {
				 uncle = grandparent->_right;
			 }
			 else
			 {
				 uncle = grandparent->_left;
			 }

			  //开始根据不同的情况处理
			  if(uncle && uncle->_col == RED)      //叔叔节点存在且为红的处理
			  {
				 uncle->_col = curparent->_col = BLACK;       //u和p变黑  g变红
				 grandparent->_col = RED;
				 _root->_col = BLACK;        //可能grandparent就是根节点 在变色之后根节点变红了 此时要变回去 

				 cur = grandparent;         //让此时的grandparent为cur 并确立它的父节点 为了进行下一次的判断
				 curparent = cur->_parent;
			  }
			  else //如果是第一次进循环 这里就是uncle节点不存在的情况  如果是第二次或更多次进的循环 这里就是uncle节点存在且为黑的情况
			  {                                            //这两种情况处理的方法一样
				  if (curparent == grandparent->_left)   //p为g左的情况
				  {
					  if (cur==curparent->_right)  // 先对curparent进行左单旋   // g          g
					  {                                                   //  p          p     u
						  RotateL(curparent);                                  //c          c
						  Node* m = cur;          //curparent单旋之后 cur和curparent的位置交换了
						  cur = curparent;
						  curparent = m;
					  }                                                 //      if里面的情况在处理后变为下面
					  RotateR(grandparent);                            //   g            g
				  }                                                   //  p             p    u
				  else    // p为g右的情况                                 c             c
				  {
					  if (cur == curparent->_left) //先对curparent进行左单旋
					  {
						  RotateR(curparent);
						  Node* m = cur;
						  cur = curparent;
						  curparent = m;
					  }
					  RotateL(grandparent);
				  }
				  curparent->_col = BLACK;    //最后统一变色
				  grandparent->_col = RED;
				  return true;
			  }
		 }  //如果父节点不是红色 不需要处理 直接返回
		 return true;   //插入成功 返回true
	 }

	 void RotateR(Node* parent)
	 {
		 Node* subl = parent->_left;
		 Node* sublR = subl->_right;
		 parent->_left = sublR;   //先将subl的右给了parent的左 
		 subl->_right = parent;   //然后parent变为subl的右

		 if (sublR)
		 {
			 sublR->_parent = parent;
		 }
		 Node* pparent = parent->_parent;       //在改变parent的parent指针之前先存一下
		 parent->_parent = subl;  //还需要改变parent的parent指针
		 //处理pparent的指向问题
		 if (pparent)              //pparent不为空就让pparent指向subl
		 {
			 if (pparent->_left == parent)
			 {
				 pparent->_left = subl;
			 }
			 else
			 {
				 pparent->_right = subl;
			 }
		 }
		 else   //如果pparent为空 说明parent就是根节点 那么直接更新根节点为parent
		 {
			 _root = subl;
		 }
		 subl->_parent = pparent;
	 }

	 void RotateL(Node* parent)
	 {
		 Node* subl = parent->_right;
		 Node* sublL = subl->_left;
		 parent->_right = sublL;
		 subl->_left = parent;

		 if (sublL)
		 {
			 sublL->_parent = parent;
		 }

		 Node* pparent = parent->_parent;
		 parent->_parent = subl;

		 if (pparent)
		 {
			 if (pparent->_left == parent)
			 {
				 pparent->_left = subl;
			 }
			 else
				 pparent->_right = subl;
		 }
		 else
		 {
			 _root = subl;
		 }
		 subl->_parent = pparent;

	 }

	 Node* Find(const K& key)
	 {
		 Node* cur = _root;
			 while (cur)
			 {
				 if (cur->_kv.first < key)
				 {
					 cur = cur->_right;
				 }
				 else if (cur->_kv.first > key)
				 {
					 cur = cur->_left;
				 }
				 else
				 {
					 return cur;
				 }
			 }
		 return nullptr;
	 }

	 bool Check(Node* root, int blackNum, const int refNum)
	 {
		 if (root == nullptr)
		 {
			 //  前序遍历⾛到空时，意味着⼀条路径⾛完了
				 if (refNum != blackNum)          //判断这条路径的黑色节点和某一天路径的节点是否相同
				 {                                         //检查第四点规则
					 cout << " 存在黑色节点的数量不相等的路径 " << endl;
						 return false;
				 }
			 return true;
		 }
		 // 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了
			 if (root->_col == RED && root->_parent->_col == RED)         //检查第三点规则
			 {
				 cout << root->_kv.first << " 存在连续的红⾊结点 " << endl;
					 return false;
			 }
		 if (root->_col == BLACK)
		 {
			 blackNum++;
		 }
			 return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
	 }
	 bool IsBalance()
	 {
		 if (_root == nullptr)
			 return true;
		 if (_root->_col == RED)   //检查第二点规则
			 return false;
		
           int refNum = 0;    //  参考值
		 Node* cur = _root;
		 while (cur)
		 {
			 if (cur->_col == BLACK)         //遍历最左边路径 统计黑色节点个数
			 {
				 ++refNum;
			 }
			 cur = cur->_left;
		 }
		 return Check(_root, 0, refNum);
	 }

	 void Midbl()    //中序遍历的形参类型需要为节点  但是我们创建的对象是BStree类型 且里面的root根节点为私有
	{                         //所以 我们可以提供一个返回根节点的函数 或者像之前实现归并非递归那样做一层封装
		Midbl1(_root);
	}
		
	void Midbl1(Node* root)   //中序遍历  先左再中再右 对搜索二叉树来说也就是从小到大的顺序打印
	{
		if (root == nullptr)
		{
			return;
		}
		Midbl1(root->_left);
		cout << root->_kv.first << " ";
		Midbl1(root->_right);
	}
private:
	Node* _root = nullptr;
};